/**
 * 在给定的网格中，每个单元格可以有以下三个值之一：
 *  值 0 代表空单元格；
 *  值 1 代表新鲜橘子；
 *  值 2 代表腐烂的橘子。
 * 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
 * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
 */
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
/**
 * Solution 1:BFS
 */
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        // grid维度
        int m = grid.size();
        int n = grid[0].size();

        // 四个方向
        vector<pair<int,int>> around = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        vector<vector<int>> minute(m, vector<int>(n, -1));
        //记录初始新鲜橘子个数
        int fresh = 0;
        int ans = 0;

        queue<pair<int,int>> que;

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 2){
                    que.push({i,j});
                    minute[i][j] = 0;                
                }
                else if(grid[i][j] == 1){
                    fresh += 1;
                }
            }
        }

        int a = 0;
        while(!que.empty()){
            auto head = que.front();
            que.pop();
            for(int k=0; k<4; k++){
                int x = head.first + around[k].first;
                int y = head.second + around[k].second;
                // 判断这些周围点在不在矩阵范围内
                if(x<0 || x>=m || y<0 || y>=n || grid[x][y]==2 || grid[x][y]==0) continue;
                minute[x][y] = minute[head.first][head.second] + 1;
                que.push({x,y});
                if(grid[x][y] == 1){
                    fresh -= 1;
                    ans = minute[x][y];
                    if(!fresh) break;
                }
            }
        }
        return fresh ? -1 : ans;
    }
};